🥖 2차원 격자에서 연결된 덩어리 착기

2차얼 격자 문제에서 상하좌우로 연결된 영역(덩어리)의 문제들은 섬 개수, 영역 크기 계산, 퍼짐 시뮬레이션 등 다양한 문제에서 반복적으로 등장합니다.

핵심은 BFS 또는 DFS를 이용하여 연결된 영역을 한 번에 탐색하는 것입니다.

1️⃣ 핵심 개념

🔹 연결된 덩어리란?

• 상, 하, 좌, 우로 이어진 동일한 값의 집합
• 하나의 시작점에서 BFS/DFS를 수행하면 하나의 덩어리를 전부 방문 가능

🔹 기본 문제 패턴

1. 격자를 전체 순회
2. 아직 방문하지 않은 특정 값(예: 1)을 발견
3. BFS/DFS 시작
4. 연결된 영역 전부 방문 처리
5. BFS/DFS 1회 = 덩어리 1개

🔹 거의 등장하는 요소

• 방문 배열 (visited)
• 방향 배열 (dx, dy)
• 범위 체크 (nx >= 0 ...)

2️⃣ 예시 문제 - 섬의 개수 구하기

📄 문제

2차원 격자 grid가 주어진다.

• "1" → 땅
• "0" → 바다

상하좌우로 연결된 땅은 하나의 섬이다. 섬의 개수를 구하시오.

입력
[
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]

출력
3

💡 풀이 아이디어

• 격자를 전체 탐색
• 방문하지 않은 "1" 발견 시 BFS 시작
• 연결된 모든 "1" 방문 처리
• BFS 횟수 = 섬 개수

🧐 예시 코드

function solution(grid) {
	const n = grid.length;
	const m = grid[0].length;

	const visited = Array.from({ length: n }, () => Array(m).fill(false));

	cosnt dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]] //상,하,좌,우
	let answer = 0;

	for (let i = 0; i < n; i++) {
		for (let j = 0; j < m; j++) {
			if (grid[i][j] === "1" && !visited[i][j]) { // 섬 체크 & 미방문
				answer++; // 덩어리 초기 진입 시 개수 체크

				const queue = [[i, j]];
				visited[i][j] = true;

				while (queue.length) {
					cosnt [x, y] = queue.shift();

					for (let [dx, dy] of [dirs]) {
						const nx = x + dx;
						const ny = y + dy;

						if (nx >= 0 && ny >= 0 && nx < n && ny < m && grid[nx][ny] === "1" && !visited[i][j]) {
							visited[i][j] = true;
							queue.push([nx, ny]);
						}
					}
				}
			}
		}
	}

	return ansewr;
}

✍️ 한 줄 정리

격자에서 연결된 영역을 찾느 문제는 전체 순회 + BFS/DFS 한 번이 곧 덩어리라는 관점으로 접근